package src.sort;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author starsea
 * @date 2024-06-23 23:02
 */

/**
 * 时间复杂度：
 * 最好情况：O(n*log2^n)
 * 最坏情况：O(N^2)
 * 空间复杂度：O(1)
 * 稳定性：不稳定
 *
 *
 * @author starsea
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));

    }

    public static int[] shellSort(int[] arr) {
        int len = arr.length;
        List list=new ArrayList();
        while (len > 1) {
            len /= 2;
            for (int i = len; i < arr.length; i++) {
                int index = arr[i];
                int j = i - len;
                for (; j >= 0; j -= len) {
                    if (arr[j] >= index) {
                        arr[j + len] = arr[j];
                    } else {
                        break;
                    }
                }
                arr[j + len] = index;
            }
            System.out.println(Arrays.toString(arr));
        }
        return arr;
    }

}
